[리트코드]_42.Trapping_Rain_Water
💯 solving-algo | February 17, 2021
문제 주소
높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하는 문제 https://leetcode.com/problems/trapping-rain-water/
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
volume = 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
while left < right:
left_max, right_max = max(height[left], left_max), \
max(height[right], right_max)
if left_max <= right_max:
volume += left_max - height[left]
left += 1
else:
volume += right_max - height[right]
right -= 1
return volume풀이방법
투 포인터를 이용해 풀었다. 가장 높이 있는 벽을 왼쪽과 오른쪽으로 나누는 기준점으로 삼고, 가장 높은 벽에 둘 다 도달하였을 때 종료된다.
또한, volume 변수에 현재 가장 높은 벽 - 다음 낮은 벽 일 경우 물이 차오를 수 있는 구조기 때문에 그 차이 값만큼 더해 주었다.
